import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * Description:请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。
 * 实现 LRUCache 类：
 * LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
 * int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
 * void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；
 * 如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
 * 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
 * User: wangxin
 * Date: 2025-03-25
 * Time: 22:05
 */
public class Test {
    class LRUCache {
        class DLinkedNode{
            int key;
            int value;
            DLinkedNode pre;
            DLinkedNode next;
            public DLinkedNode(){}
            public DLinkedNode(int _key,int _value){
                key = _key;
                value = _value;
            }
        }
        private Map<Integer,DLinkedNode> cahe = new HashMap<>();
        private int size;
        private int capacity;
        private DLinkedNode head,tail;
        public LRUCache(int capacity) {
            this.size = 0;
            this.capacity = capacity;
            head = new DLinkedNode();
            tail = new DLinkedNode();
            head.next = tail;
            tail.pre = head;
        }

        public int get(int key) {
            DLinkedNode node = cahe.get(key);
            if(node == null){
                return -1;
            }
            moveToHead(node);
            return node.value;
        }

        public void put(int key, int value) {
            DLinkedNode node = cahe.get(key);
            if(node == null){
                DLinkedNode newNode = new DLinkedNode(key,value);
                cahe.put(key,newNode);
                addToHead(newNode);
                ++size;
                if(size > capacity){
                    DLinkedNode tail = removeTail();
                    cahe.remove(tail.key);
                    --size;
                }
            }else{
                node.value = value;
                moveToHead(node);
            }
        }
        public void addToHead(DLinkedNode newNode){
            newNode.pre = head;
            newNode.next = head.next;
            head.next.pre = newNode;
            head.next = newNode;
        }
        public void removeNode(DLinkedNode node){
            node.pre.next = node.next;
            node.next.pre = node.pre;
        }
        public void moveToHead(DLinkedNode node){
            removeNode(node);
            addToHead(node);
        }
        public DLinkedNode removeTail(){
            DLinkedNode res = tail.pre;
            removeNode(res);
            return res;
        }
    }
}
